Genetic algorithms provide a technique for solving optimization problems that are based on natural selection, the process that drives biological evolution. Genetic algorithms may be used to solve optimization problems in the aerospace industry, structural design problems and civil engineering problems. A genetic algorithm iteratively modifies a population of individual solutions in order to create a new population. At each generation, the genetic algorithm selects better individuals from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population “evolves” toward an “optimal solution. A genetic algorithm uses three main types of operations to create the next population from the current population namely elites, crossover, and mutation. Elites are individuals selected intact from the current population. Crossover is a technique to swap content from individuals in the current population to create new individuals for the next generation. The mutation operation is of special interest for the current discussion.
In a genetic algorithm, a mutation operator is a genetic operator used to maintain diversity in a population from one generation to the next. An example of a mutation operator involves the probability that some arbitrary element in a point vector (individual) will be changed from its original state. FIG. 1 illustrates a mutation example in which two elements are randomly chosen and changed to a random value. A point vector A (10) includes elements 11, 12, 13, 14 and 15. A second point vector B (20) is also shown where B is an example of an individual selected by mutating selected elements within point vector A. Point vector B (20) includes elements 21, 22, 23, 24 and 25. Element 11 was mutated into element 21 and Element 15 was mutated into element 25. The values of elements 12, 13 and 14 is the same of that of respective elements 22, 23 and 24. The mutation of the individuals helps prevent premature convergence in the overall population.
FIG. 2 illustrates in a graph 30 the effect of a mutation operation in a conventional unconstrained optimization problem with two decision variables. An individual P2 (34) is generated via a mutation operation on current individual P1 (32) in an unconstrained optimization problem.
Unfortunately, while existing mutation algorithms (or operators), such as uniform random mutation and Gaussian mutation, are very useful in unconstrained optimization, it is very difficult to perform a mutation operation in a linear or bound constrained optimization while maintaining feasibility (a feasible individual represents a possible solution to the problem being optimized). For example, in FIG. 3, a graph 40 depicts two linear constraints 46 and 48 and a point P1 (42). Conventional mutation operators that do not take into account the linear constraints 46 and 48 may generate an individual P2 (44) that is located outside the feasible region 50 and therefore not usable as a possible solution to the optimization problem.